﻿using Client.MirObjects;
using Client.MirScenes;
using Microsoft.DirectX.DirectSound;
using Microsoft.DirectX.PrivateImplementationDetails;
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.Windows.Forms.VisualStyles;

namespace Client.Command
{
    enum NodeTag
    {
        New=1,
        Open=2,
        Close=3
    }

    internal class NodeD : IHeapItem<NodeD>
    {
        private int k = 0, h = 0;
        public int KCost { get => Math.Min(k, h); }

        public int HCost { get => h; set => h = value; }
        
        public NodeTag tag = NodeTag.New;
        public Point Location;
        private MapControl Map;
        public NodeD Parent;

        private int _heapIndex;
        private ushort[] cost=new ushort[8];
        public NodeD(MapControl map,int x,int y)
        {
            this.Map = map;
            Location = new Point(x, y);
            cost = new ushort[8];
            //不玩循环这种花里胡哨的，上，右上，右，右下，下，左下，左，左上
            for (int i = 0; i < 8; i++)
            {
                if ((i & 1) == 0)
                    cost[i] = 10;
                else
                    cost[i] = 14;
            }
        }

        public bool Walkable
        {
            get { return Map.EmptyCell(Location); }
        }
        public int HeapIndex { 
            get => _heapIndex;
            set => _heapIndex = value;
        }
        
        /// <summary>
        /// 暂时设定，不是邻居返回10000，不可到达返回10000
        /// </summary>
        /// <param name="from"></param>
        /// <returns></returns>
        public ushort CostCGet(Point from)
        {
            MirDirection dir = Functions.DirectionFromPoint(from, this.Location);
            return cost[(int)dir];
        }
        public ushort CostCGet(NodeD from)
        {
            var point = from.Location;
            return CostCGet(point);
        }
        public ushort SumCostFrom(NodeD from)
        {
            return (ushort)(CostCGet(from) + HCost);
        }
        public void CostCSet(Point from,ushort cost)
        {
            MirDirection dir = Functions.DirectionFromPoint(from, this.Location);
            this.cost[(int)dir]=cost;
        }
        
        public int CompareTo(NodeD nodeToCompare)
        {
            int compare = KCost.CompareTo(nodeToCompare.KCost);
            if (compare == 0)
            {
                compare = KCost.CompareTo(nodeToCompare.KCost);
            }
            return -compare;
        }
    }
    class PathFinderD
    {
        private NodeD[,] Grid;

        public MapControl Map;

        Heap<NodeD> openSet;
        HashSet<NodeD> closedSet;
        public int MaxSize
        {
            get { return Map.Width * Map.Height; }
        }


        public PathFinderD(MapControl map)
        {
            Map = map;

            CreateGrid();
        }

        private void CreateGrid()
        {
            Grid = new NodeD[Map.Width, Map.Height];

            for (int x = 0; x < Map.Width; x++)
            {
                for (int y = 0; y < Map.Height; y++)
                {
                    Grid[x, y] = new NodeD(Map, x, y);
                }
            }
        }

        /// <summary>
        /// 和A*不同D*为反向追踪
        /// </summary>
        /// <param name="start"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public IEnumerable<NodeD> IniPath(Point start, Point target)
        {
            //搜索四周是不是无效点
            var tempPoint = target;
            for (int i = 0; i < 8 && !GameScene.Scene.MapControl.EmptyCell(tempPoint); i++)
            {
                tempPoint = Functions.PointMove(tempPoint, (MirDirection)i, 1);
            }
            target = tempPoint;

            NodeD startState = GetNode(start);
            NodeD goalState = GetNode(target);
            openSet= new Heap<NodeD>(MaxSize);
            closedSet = new HashSet<NodeD>();
            openSet.Add(goalState);
            goalState.HCost = 0;
            int kim = -1;
            //初始探路
            do
            {
              kim = ProcessState();
            } while (kim!=-1&&closedSet.Last().Location!=start);
            if(closedSet.Last().Location==start)
            {
                return RetracePath(startState, goalState);
            }
            return null;
        }

        public void UpdatePath(NodeD next)
        {
            modifyCost(next.Parent, next);
            NodeD y = next.Parent;
            int kmin = -1;
            do
            {
                kmin = ProcessState();
            } while (y.KCost<y.HCost&&kmin!=-1);
        }
        public void modifyCost(NodeD start,NodeD next,int maxCost=1000)
        {
            next.CostCSet(start.Location, 1000);
            if(next.tag==NodeTag.Close)
            {
                next.tag = NodeTag.Open;
                Insert(next, next.HCost);
            }
        }
        public int ProcessState()
        {
            if (openSet.Count <= 0)
                return -1;
            var x = openSet.RemoveFirst();
            var kOld = x.KCost;
            if (kOld < x.HCost)
            {
                foreach (var y in GetNeighbours(x))
                {
                    if (y.HCost < kOld && x.HCost > y.HCost + y.CostCGet(x.Location))
                    {
                        x.Parent = y;
                        x.HCost = y.HCost + y.CostCGet(x.Location);
                    }
                }
            }

            if (kOld == x.HCost)
            {
                foreach (var y in GetNeighbours(x))
                {
                    if (y.tag == NodeTag.New || (
                        (y.Parent == x && y.HCost != x.SumCostFrom(y) ||
                        (y.Parent != x) && y.HCost > x.SumCostFrom(y)))
                        )
                    {
                        y.Parent = x;
                        Insert(y, x.HCost + x.CostCGet(y));
                    }
                }
            }
            else
            {
                foreach (var y in GetNeighbours(x))
                {
                    if (y.tag == NodeTag.New ||
                        (y.Parent == x && y.HCost != x.SumCostFrom(y)))
                    {
                        y.Parent = x;
                        Insert(y, x.HCost + x.CostCGet(y));
                    }
                    else
                    {
                        if(y.Parent!=x&&y.HCost>x.SumCostFrom(y))
                        {
                            Insert(y, x.SumCostFrom(y));
                        }
                        else
                        {
                            if((y.Parent!=x&&x.HCost>y.HCost+y.SumCostFrom(x))&&y.tag==NodeTag.Close&&y.HCost>kOld)
                            {
                                Insert(y, y.HCost);
                            }
                        }
                    }
                }
            }
            var backInfo = openSet.First();
            return backInfo==default(NodeD)?-1:backInfo.KCost;
        }

        public void  Insert(NodeD node,int hnew)
        {
            node.HCost = hnew;
            node.tag = NodeTag.Open;
            openSet.Add(node);
        }

        /// <summary>
        /// 在路径未改变的是时候，endNode是targetNode的特殊情况
        /// </summary>
        /// <param name="startNode"></param>
        /// <param name="endNode"></param>
        /// <returns></returns>
        public IEnumerable<NodeD> RetracePath(NodeD startNode, NodeD endNode)
        {
            Queue<NodeD> path = new Queue<NodeD>();
            NodeD current = endNode;

            while (current != startNode)
            {
                path.Enqueue(current);
                current = current.Parent;
            }
            path.Enqueue(startNode);
            return path.Reverse();
        }

        private int GetDistance(Node nodeA, Node nodeB)
        {
            int distX = Math.Abs(nodeA.Location.X - nodeB.Location.X);
            int distY = Math.Abs(nodeA.Location.Y - nodeB.Location.Y);

            if (distX > distY)
                return 14 * distY + (10 * (distX - distY));

            return 14 * distX + (10 * (distY - distX));
        }

        private NodeD GetNode(Point location)
        {
            return Grid[location.X, location.Y];
        }

        private List<NodeD> GetNeighbours(NodeD node)
        {
            List<NodeD> neighbours = new List<NodeD>();
            for (int x = -1; x <= 1; x++)
            {
                for (int y = -1; y <= 1; y++)
                {
                    if (x == 0 && y == 0) continue;

                    int checkX = node.Location.X + x;
                    int checkY = node.Location.Y + y;

                    if (checkX >= 0 && checkX < Grid.GetLength(0) && checkY >= 0 && checkY < Grid.GetLength(1))
                    {
                        neighbours.Add(Grid[checkX, checkY]);
                    }
                }
            }

            return neighbours;
        }
    }
}
